{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Decode String（解码字符串）\n",
    "\n",
    "[@mjd507][1] ｜ [WeChat Channel（微信公众号）][2]\n",
    "\n",
    "![Logo](images/Day71-1.png)\n",
    "\n",
    "[1]: https://github.com/mjd507\n",
    "[2]: https://mp.weixin.qq.com/s/6xGMjn-yqJAyLexaDfFKnQ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string with a certain rule: `k[string]` should be expanded to `string` $k$ times. So for example, `3[abc]` should be expanded to `abcabcabc`. Nested expansions can happen, so `2[a2[b]c]` should be expanded to `abbcabbc`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个遵循特定规则的字符串：`k[string]`需要被转换为`string`重复$k$次。所以，字符串`3[abc]`应该被展开为`abcabcabc`。嵌套表达式有可能出现，所以`2[a2[b]c]`应该被展开为`abbcabbc`。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Starting Point（初始模板）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decodeString(s: str) -> str:\n",
    "    stack = ['']\n",
    "    for char in s:\n",
    "        if char.isdigit():\n",
    "            if type(stack[-1]) == str: \n",
    "                stack.append(int(char))\n",
    "            else:\n",
    "                stack[-1] = 10 * stack[-1] + int(char)\n",
    "        elif char == '[':\n",
    "            stack.append('')\n",
    "        elif char == ']':\n",
    "            substr = stack.pop()\n",
    "            repeats = stack.pop()\n",
    "            stack[-1] += (substr * repeats)\n",
    "        else:\n",
    "            stack[-1] += char\n",
    "    return stack[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test Cases（测试样例）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'abbbbbbbbbbbbccccccccabbbbbbbbbbbbccccccccabbbbbbbbbbbbcccccccc'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "decodeString('3[a12[b]8[c]]')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
